題目

題目大意

給一個陣列 nums 描述一個頭尾相連的環，在選擇一個數字後，其左右一個數字都不能選取 (拿 index = 1 的數字時，index = 0 和 index = 2 的數字都不能拿)，求拿取的數字的最大和。

想法

這題的第一個版本是單純的陣列而不是環，用遞迴的話可以想到是對取 k 的值 + 遞迴 k + 2 跟不取 k 的值去遞迴 k + 1兩者的答案取 max，因為會有大量重複計算的部分，可以開個陣列去 DP 他。
變成環後，會發現可以分成從頭開始不要取到尾和從第二個開始可以取到尾，有些人會想用一個 bool 去分狀態，但這樣分 code 太醜，可以把原本的參數多紀錄一個 n (大小) 就好了。
每個 index 進去後只會 dp 一次，時間複雜度 O(nums.length())；額外開兩個大小為 nums.length 的陣列，空間複雜度 O(nums.length())。

Code(C++)

int solve(vector<int>& nums, vector<int>& dp, int id, const int& n) {
    if (id >= n) return 0;
    if (dp[id] != -1) return dp[id];
    return dp[id] = max(nums[id] + solve(nums, dp, id + 2, n), solve(nums, dp, id + 1, n));
}
int rob(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return nums[0];
    vector<int>dp1(n, -1), dp2(n, -1);
    return max(solve(nums, dp1, 0, n - 1), solve(nums, dp2, 1, n));
}

心得

前幾天才有學弟問我 House Robber (好像是 daily challenge)，今天 pick one 就抽到進階版，這是什麼緣分XD